package com.leetcode.easy;

/**
 * @Classname SolutionMySqrt
 * @Description TODO
 * @Date 2020/8/24 19:12
 * @Created by zfl
 */
public class SolutionMySqrt {
    /*设计自己的平方根函数
    *@Description
    *@param [x]
    *@return int
    * 执行用时：2 ms, 在所有 Java 提交中击败了60.80%的用户
    * 内存消耗37.1 MB, 在所有 Java 提交中击败了40.41%的用户
    */
    public int mySqrt(int x) {
        //x = 0 || 1
        if(x <= 1) return x;
        //2 - 5
        if(x <= 5) return x / 2;
        int hi = x / 2;
        int lo = 1;
        int mid = 0;
        while (hi > lo + 1) {
            mid = lo + (hi - lo) / 2;
            //用mid > x / mid 而不是mid * mid > x避免内存溢出
            if(mid > x / mid) {
                hi = mid;
            }else if(mid < x / mid) {
                lo = mid;
            }else {
                return mid;
            }
        }
        return lo;
    }
}
